package zuo.algo.c13;

import zuo.algo.util.StringUtils;

import java.util.Random;

/**
 * 00:03-求最长回文字串
 */
public class Palindrome {

    public static int max(String str) {
        char[] char1 = str.toCharArray();
        char[] char2 = new char[char1.length * 2 + 1];
        int res = -1;
        for (int i = 0; i < char1.length; i++) {
            char2[2 * i] = '#';
            char2[2 * i + 1] = char1[i];
        }
        char2[char2.length - 1] = '#';
        for (int i = 0; i < char2.length; i++) {
            int temp = 1;
            int l = i - 1, r = i + 1;
            while (l >= 0 && r < char2.length) {
                if (char2[l] != char2[r]) {
                    break;
                }
                l--;
                r++;
                temp += 2;
            }
            res = Math.max(res, temp);
        }
        return res / 2;
    }

    public static int manacher(String str) {
        char[] chars1 = str.toCharArray();
        char[] chars2 = new char[chars1.length * 2 + 1];
        for (int i = 0; i < chars1.length; i++) {
            chars2[i * 2] = '#';
            chars2[i * 2 + 1] = chars1[i];
        }
        chars2[chars2.length - 1] = '#';

        int[] resArr = new int[chars2.length];
        int left = -1, right = -1, idx = -1;
        for (int i = 0; i < chars2.length; i++) {
            if (i >= right) {
                int l = i - 1, r = i + 1;
                while (l >= 0 && r < chars2.length) {
                    if (chars2[l] != chars2[r]) {
                        break;
                    }
                    l--;
                    r++;
                }
                resArr[i] = r - l - 1;
                left = l + 1;
                right = r - 1;
                idx = i;
            } else {
                int lIdx = 2 * idx - i;
                int val = lIdx - (resArr[lIdx] / 2);
                if (val > left) {
                    resArr[i] = resArr[lIdx];
                } else if (val < left) {
                    resArr[i] = (right - i) * 2 + 1;
                } else {
                    int l = 2 * i - right, r = right;
                    while (l >= 0 && r < chars2.length) {
                        if (chars2[l] != chars2[r]) {
                            break;
                        }
                        l--;
                        r++;
                    }
                    resArr[i] = r - l - 1;
                    if (r > right + 1) {
                        left = l + 1;
                        right = r - 1;
                        idx = i;
                    }
                }
            }
        }

        int maxVal = -1;
        for (int i : resArr) {
            maxVal = Math.max(i, maxVal);
        }
        return maxVal / 2;
    }

    public static void main(String[] args) {
        String str1 = "angngggns";
        int i1 = max(str1);
        int i2 = manacher(str1);
        System.out.println(i1 + ":" + i2);
        Random random = new Random();
        for (int i = 0; i < 1000000; i++) {
            int len = (random.nextInt(100) + 2) * 1;
            String str = StringUtils.getRandomStr(len);
            int idx1 = max(str);
            int idx2 = manacher(str);
            if (idx1 != idx2) {
                System.out.println(str);
                throw new RuntimeException();
            }
            System.out.println(i);
        }
    }
}
